package 监控二叉树;

/**
 * createTime: 2025/4/27 18:48
 * description:
 *
 * @author AirMan
 */
public class Solution {
    public int minCameraCover(TreeNode root) {
        // greedy ! ! !
        // 本题有一个非常重要的线索需要发现：摄像头安装在根节点只能省下一个摄像头，但是摄像头安装在叶子结点的父节点
        // 省下的摄像头屎指数级别的，想象一个深度很深的完全二叉树，如果摄像头安装在叶子节点的父节点上所带来的效果！
        // 局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

        // 本题的难点就在于如果进行遍历了，想要找到叶子节点的父节点，我们可以采用中序遍历（左根右）
        // 当节点的左右孩子都是null的时候返回标记1，接住1的这个节点就是叶子节点的父节点了
        // 如果为父节点安装了监控，我们应该进一步返回2，接住2的这个节点代表不需要再安装监控了，并返回1给上一层的节点
        // 上一层如果接受到1，那就安装监控，然后继续返回2给上一层

        // 如下三种：
        // 该节点无覆盖        0：该节点无覆盖
        // 本节点有摄像头      1：本节点有摄像头
        // 本节点有覆盖        2：本节点有覆盖
        // 空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了
        // 情况 ①：左右子树均是已覆盖状态 ==> 不安插摄像头，并返回状态0给父节点
        // 情况 ②：左右子树有一个是未覆盖 ==> 安插摄像头，返回状态1
        // 情况 ③：左右子树一个是已安装摄像头，另一个是已覆盖或已安装摄像头 ==> 不安插摄像头，返回状态2
        // 情况 ④：递归结束，头结点没有覆盖 ==> 安插摄像头

        if (greedyPostOrder(root) == 0) {
            count++;
        }
        return count;
    }

    private int count = 0;

    private int greedyPostOrder(TreeNode root) {
        if (root == null) {
            return 2;
        }
        // left
        int left = greedyPostOrder(root.left);
        // right
        int rihgt = greedyPostOrder(root.right);
        // inorder
        if (left == 2 && rihgt == 2) {
            return 0;
        } else if (left == 0 || rihgt == 0) {
            count++;
            return 1;
        } else if (left == 1 || rihgt == 1) {
            return 2;
        } else {
            // 这个 return -1 逻辑不会走到这里
            return -1;
        }
    }
}
